#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "arbre_r&n.h"


struct arbre_rn {
  noeud racine;
};

struct noeud {
  noeud fd;
  noeud fg;
  noeud pere;
  int donnee;
  char couleur;
};

extern arbre_rn arbre_rn_creer(){
  arbre_rn self = malloc(sizeof(struct arbre_rn));
  self->racine = NULL;
  return self;
}

static noeud noeud_creer(int donnee){
  noeud self = malloc(sizeof(struct noeud));
  self->donnee = donnee;
  self->fd = NULL;
  self->fg = NULL;
  self->pere = NULL;
  self->couleur = 'r';
  return self;
}


/*******************************************/
/*************** ACCESSEURS ****************/
/*******************************************/

static int est_racine(arbre_rn a, noeud n){
  return a->racine == n;
}

static noeud pere(noeud n){
  return n->pere;
}

static noeud grand_pere(arbre_rn a, noeud n){
  if(est_racine(a, n))
    return NULL;
  else return n->pere->pere;
}

static noeud oncle(arbre_rn a, noeud n){
  noeud g = grand_pere(a, n);
  if(g == NULL)
    return NULL;
  if(n->pere == g->fg)
    return g->fd;
  else return g->fg;
}

static char couleur(noeud n){
  return n->couleur;
}

static int est_fils_droit(arbre_rn a, noeud n){
  if(n->donnee > n->pere->donnee)
    return 1;
  else return 0;
}

static int est_fils_gauche(arbre_rn a, noeud n){
  if(n->donnee <= n->pere->donnee)
    return 1;
  else return 0;
}

static int est_rouge(noeud n){
  if(n != NULL)
    return n->couleur == 'r';
  else return 0;
}

static int est_noir(noeud n){
  if(n != NULL)
    return n->couleur == 'n';
  else return 0;
}



/*******************************************/
/************* FIN ACCESSEURS **************/
/*******************************************/





/*******************************************/
/*************** OPERATIONS ****************/
/*******************************************/

static void rotation_droite(arbre_rn a, noeud n){
  noeud tmp = n->fd;
  noeud tmp_pere = grand_pere(a, n);
  n->fd = pere(n);
  n->fd->fg = tmp;
  n->fd->pere = n;
  n->pere = tmp_pere;

  if(tmp_pere == NULL)
    a->racine = n;
  else if(est_fils_gauche(a, n))
    tmp_pere->fg = n;
  else
    tmp_pere->fd = n;      
}

static void rotation_gauche(arbre_rn a, noeud n){
  noeud tmp = n->fg;
  noeud tmp_pere = grand_pere(a, n);
  n->fg = pere(n);
  if(n->fg != NULL){
    n->fg->fd = tmp;
    n->fg->pere = n;
  }
  n->pere = tmp_pere;
  if(tmp_pere == NULL)
    a->racine = n;
  else if(est_fils_gauche(a, n))
    tmp_pere->fg = n;
  else
    tmp_pere->fd = n;
}

static void reorganiser_arbre(arbre_rn a, noeud n){
  if(!est_racine(a, pere(n))){
    noeud o = oncle(a, n);
    if(est_rouge(o)){
      n->pere->couleur = o->couleur = 'n';
      n->pere->pere->couleur = 'r';
      if(pere(grand_pere(a, n)) != NULL && couleur(grand_pere(a, n)) == 'r')
	reorganiser_arbre(a, grand_pere(a, n));
    }
    else {
      if(est_fils_gauche(a, n) && est_fils_gauche(a, pere(n))){ //CAS 1a
	n->pere->couleur = 'n';
	n->pere->pere->couleur = 'r';
	rotation_droite(a, pere(n));    
      }
      
      else if(est_fils_droit(a, n) && est_fils_droit(a, pere(n))){ //CAS 1b
	n->pere->couleur = 'n';
	n->pere->pere->couleur = 'r';
	rotation_gauche(a, pere(n));
      }
      
      else if(est_fils_droit(a, n) && est_fils_gauche(a, pere(n))){ //CAS 2a
	n->couleur = 'n';
	n->pere->pere->couleur = 'r';
	rotation_gauche(a, n);
	rotation_droite(a, pere(n));
      }
      
      else if(est_fils_gauche(a, n) && est_fils_droit(a, pere(n))){ //CAS 2b
	n->couleur = 'n';
	n->pere->pere->couleur = 'r';
	rotation_droite(a, n);
	rotation_gauche(a, pere(n));
      }
    }
  }
}

/*******************************************/
/************* FIN OPERATIONS **************/
/*******************************************/




/*******************************************/
/********** INSERTION-SUPPRESSION **********/
/*******************************************/

static void inserer_aux(arbre_rn a, noeud n, int donnee){
  
  if(a->racine == NULL){ // Cas arbre vide
    a->racine = noeud_creer(donnee);
    a->racine->couleur = 'n';
  }
  else{ // Cas arbre non vide
    if(donnee <= n->donnee){ // Cas insertion sur fils gauche
      if(n->fg == NULL){
	n->fg = noeud_creer(donnee);
	n->fg->pere = n;
	if(couleur(n) == 'r')
	  reorganiser_arbre(a, n->fg);
      }
      else
	inserer_aux(a, n->fg, donnee);
    }
    else if(donnee > n->donnee) // Cas insertion sur fils droit
      if(n->fd == NULL){
	n->fd = noeud_creer(donnee);
	n->fd->pere = n;
	if(couleur(n) == 'r')
	  reorganiser_arbre(a, n->fd);
      }
      else
	inserer_aux(a, n->fd, donnee);
  }
  a->racine->couleur = 'n';
}

extern void inserer(arbre_rn a, int donnee){
  inserer_aux(a, a->racine, donnee);
}

/*******************************************/
/******** FIN INSERTION-SUPPRESSION ********/
/*******************************************/

static void affiche_noeud(noeud n){
  if(n != NULL){
    printf("Noeud %d \t Couleur %c \t", n->donnee, n->couleur);
    printf("Fils Gauche \t");
    if(n->fg != NULL)
      printf("%d \t", n->fg->donnee);
    else printf("NULL \t");
    printf("Fils Droit \t");
    if(n->fd != NULL)
      printf("%d \t", n->fd->donnee);
    else printf("NULL \t");
  }
  printf("\n");
}

static void arbre_rn_afficher_aux(arbre_rn a, noeud n){
  if(a->racine == NULL)
    printf("Arbre vide\n");
  else{
    affiche_noeud(n);
    if(n->fg != NULL)
      arbre_rn_afficher_aux(a, n->fg);
    if(n->fd != NULL)
      arbre_rn_afficher_aux(a, n->fd);
  }
}

extern void arbre_rn_afficher(arbre_rn a){
  arbre_rn_afficher_aux(a, a->racine);
}

int main(int argc, char * argv[]){

  arbre_rn a = arbre_rn_creer();
  
  
  inserer(a, 5);
  inserer(a, 53);
  inserer(a, 38);
  inserer(a, 59);
  inserer(a, 6);
  inserer(a, 19);
  inserer(a, 67);
  
  arbre_rn_afficher(a);
  
  return EXIT_SUCCESS;
}
